package com.swak.algs;

import com.swak.algs.array.Prints;

/**
 * 归并排序: 无序数组, 时间复杂度 O(N * logN)， 二分的思想
 * 
 * 思路： <br>
 * 1. 排序<br>
 * 1.1 左边有序、右边有序<br>
 * 2. 合并<br>
 * 2.1 拷贝左边，拷贝右边
 * 
 * @author lifeng
 */
public class Code15 {

	static void process(int[] arr, int L, int R) {

		/*
		 * 退出条件：只有一个数，肯定是有序的
		 */
		if (L == R) {
			return;
		}

		int mid = (L + R) >> 1;

		/*
		 *  最好的方式是使用这种，因为如果L和R比较大，则会溢出
		 */
		// int mid = L + ((R - L) >> 1);

		/*
		 * 使用二分的思想保证左边有序
		 */
		process(arr, L, mid);

		/*
		 * 使用二分的思想保证右边有序
		 */
		process(arr, mid + 1, R);

		/*
		 * 归并
		 */
		merge(arr, L, mid, mid + 1, R);
	}

	/*
	 * 4, 2, 5, 1
	 * 0  1  2  3
	 */
	public static void merge(int[] arr, int L, int LR, int R, int RR) {
		int[] a2 = new int[RR - L + 1];
		int i = L;
		int j = R;
		int N = 0;
		while (i <= LR && j <= RR) {
			if (arr[i] <= arr[j]) {
				a2[N] = arr[i];
				i++;
				N++;
			} else if (arr[i] > arr[j]) {
				a2[N] = arr[j];
				j++;
				N++;
			}
		}
		while (i <= LR) {
			a2[N++] = arr[i++];
		}
		while (j <= RR) {
			a2[N++] = arr[j++];
		}
		for (int n = L; n <= RR; n++) {
			arr[n] = a2[n - L];
		}
	}

	public static void main(String[] args) {
		int[] arr = { 4, 2, 5, 1 };
		process(arr, 0, arr.length - 1);
		Prints.print(arr);
	}
}